#include <limits.h>

using namespace std;

int a = INT_MIN;

华为2016校园招聘上机笔试题：
第一题：
// 回车在缓冲区用getchar()消掉

// 输出vector<int> stu最大值:序号a-1，到b-1
// cout<<*max_element(stu.begin()+a-1,stu.begin()+b)<<endl;

// 84.最大柱状图面积
// 在vector<int> 前面使用insert()加元素： heights.insert(heights.begin(),0);

// 85.最大矩形面积
// if ('1' == matrix[i][j]) # 字符匹配兄弟

// 435.无重叠区间
// 二维vector的排序：vector<vector<int>> intervals; // n行2列的数据
// std::sort(intervals.begin(), intervals.end(), compare);
// bool compare(vector<int> a, vector<int> b){
//     return a[1]<=b[1]; // 每行第二列比较
// }

// sort排序：
// using default comparison (operator <):
// std::vector<int> myvector = {32,71,12,45,26,80,53,33};
// std::sort(myvector.begin(), myvector.begin() + 4); // (12 32 45 71),对前4个排序

// hj01 字符串输入
// char str[5001]
// gets(str); // 这个接收输入，即使str中间有空格也ok

// hj02 字符串输入
// 第一行输入字符串： char str[N]; N=10010; gets(str);
// 第二行输入字母： char x; cin>>x;
// 查找在字符串中有字母个数：
int count = 0;
for (int i = 0; str[i] != '\0'; i++)
{
  if (str[i] == x || str[i] == x + 32 || str[i] == x - 32) // 字母大小写相隔：32
}

// hj3明明的随机数
// 去重与排序的工作：unorder_map

// hj4字符串分割
str = str.substr(8);             // 一个字符串从索引8开始剩下字符都拿上
str.substr(0, 8);                // 从0开始，拿8个长度
str.append(8 - str.size(), '0'); // 在字符串后面补size个‘0’

// hj5 进制转换 16转10
// 0xA
long long num = 0;
for (int i = 2; i < str.size(); i++)
{ // i=0 对应O i=1对应X
  if (str[i] >= '0' && str[i] <= '9')
    num = num * 16 + str[i] - '0';
  else
    num = num * 16 + str[i] - 'A' + 10; // 'A‘相当于16进制中的10
}

// hj10字符个数统计
char s;
int num = 0;
int x[128] = {0};
while (cin >> s)
{
  if (int(s) >= 0 && int(s) <= 127 && x[int(s)] == 0)
  {
    num++;
    x[int(s)] = 1;
  }
}

// hj13句子逆序
reverse(str.begin(), str.end()); // end()是队尾元素
// 翻转单个单词
for (int i = 0; i < str.size(); i++)
{
  int j = i;
  // 通过i，j定位单词首尾
  while (j < str.size() && str[j] != ' ')
    j++; // 跳出循环时，j定位到相邻两个单词空格
  reverse(str.begin() + i, str.begin() + j);

  // 定位到下一个单词
  i = j;
}

// hj14字符串的字典序排序
bool cmp(const string &s1, const string &s2)
{
  return s1 < s2;
}
sort(res.begin(), res.end(), cmp);

// hj16 购物单：附属背包问题
// 处理输入，再按照0 ~1背包进行处理，在处理时，考虑多种策略

// hj21 简单密码破解
// 字典法：考虑两个字典，一个是明文字典 a[]，另一个是明文对应的加密字典 b[]
// 然后采用字典元素对应的方法，做加密或解密，实现方法为通过明文字典匹配找到字符的索引，再到通过索引去加密字典中找到对应的字符
char a[] = {"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"}; // 明文字典
char b[] = {"bcdefghijklmnopqrstuvwxyza222333444555666777788899990123456789"}; // 加密字典

// 明文字典找索引，暗文字典找字符

// hj23 删除字符串中出现最少次数的字符
// 统计次数想到 unordered_map
#include <climits> // INT_MAX

// hj25 数据分类处理
// 1.R排序 去重
sort(R.begin(), R.end());
R.erase(unique(R.begin(), R.end()), R.end()); // 去重
string strr = to_string(r);                   // int i 转 string
                                              // 其他转换方法

// hj29 字符串加解密
加密过程：明文字典找索引，密文字典找字符
解密：反之

// hj39 两个ip是否属于同一子网
unsigned int ip2a = 0, ip2b = 0, ip2c = 0, ip2d = 0;
char ch;
cin >> mask1 >> ch >> mask2 >> ch >> mask3 >> ch >> mask4;
cin >> ip1a >> ch >> ip1b >> ch >> ip1c >> ch >> ip1d;
// cin连续输入

// N皇后：
// 从第0行开始放
// base case 有检查合法性：
/ 这部分主要代码，其实跟全排列问题差不多，isValid 函数的实现也很简单：
    // 是否可以在 board[row][col] 放置皇后？
    bool
    isValid(vector<string> &board, int row, int col)
{
  int n = board.size(); // 正方形行列等, 目前此n不等于N皇后的N,此n取决与dfs到第几层
  // 检查列是否有皇后互相冲突
  for (int i = 0; i < n; i++)
  {
    if (board[i][col] == 'Q')
      return false;
  }

  // 检查右上方是否有皇后互相冲突
  for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++)
  {
    if (board[i][j] == 'Q')
      return false;
  }

  // 检查左上方是否有皇后互相冲突
  for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--)
  {
    if (board[i][j] == 'Q')
    {
      return false;
    }
  }

  return true;
}

// 数独
// 有点类似n皇后，在table里面放数，都是每行每行的放，每行放的时候
// 假设之前行放的都满足条件，每放一个数要检查isValid()